import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 给定的nums1和nums2数据,并且m,n为数组1,2的元素个数,将两个数组合并为一个升序数组
 * 注意:nums1的长度为m+n
 */
public class SolutionSort {

    @Test
    public void clibe() {
        int[] nums1 = {1, 2, 3, 0, 0, 0};
        int[] nums2 = {2, 4, 5};
        int m = 3;
        int n = 3;

        long startTime1 =  System.currentTimeMillis();
        int[] ints = sort1(nums1, m, nums2, n);
        long endTime1 =  System.currentTimeMillis();
        System.out.println("sum1=" + Arrays.toString(ints)+",使用时间:"+ (endTime1-startTime1));

        nums1 = new int[]{1, 2, 3, 0, 0, 0};
        nums2 = new int[]{2, 4, 5};

        long startTime2 =  System.currentTimeMillis();
        int[] sum2 = sort2(nums1, m, nums2, n);
        long endTime2 =  System.currentTimeMillis();
        System.out.println("sum2=" + Arrays.toString(sum2)+",使用时间:"+ (endTime2-startTime2));

        nums1 = new int[]{1, 2, 3, 0, 0, 0};
        nums2 = new int[]{2, 4, 5};
        long startTime3 =  System.currentTimeMillis();
        int[] sum3 = sort3(nums1, m, nums2, n);
        long endTime3 =  System.currentTimeMillis();
        System.out.println("sum3=" + Arrays.toString(sum3)+",使用时间:"+ (endTime3-startTime3));

    }

    /**
     * 方法一：使用jdk自带方法
     */
    public int[] sort1(int[] nums1, int m, int[] nums2, int n) {

        for (int i = 0; i < n; ++i) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
        return nums1;
    }

    /**
     * 方法2 使用双指针将两个数组放入中间数组中
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     * @return
     */
    public int[] sort2(int[] nums1, int m, int[] nums2, int n) {
        int k = m + n;
        int[] temp = new int[k];
        for (int index = 0, nums1Index = 0, nums2Index = 0; index < k; index++) {
            if (nums1Index >=m){//如果num1数组已经取完了,完全取nums2数组的值就行
                temp[index] = nums2[nums2Index++];
            }else if (nums2Index >=n){//如果num2数组已经取完了,完全取nums1数组的值就行
                temp[index] = nums1[nums1Index++];
            }else if(nums1[nums1Index]<nums2[nums2Index]){
                //如果nums1数组的元素小于nums2的元素,取nums1数组的值
                temp[index] = nums1[nums1Index++];
            }else {
                //如果nums2数组的元素小于或者等于nums1的元素,取nums2数组的值
                temp[index] = nums2[nums2Index++];
            }
        }

        for (int i = 0; i < k; i++) {
            nums1[i] = temp[i];
        }

        return nums1;
    }

    /**
     * 方法3,直接使用双指针在nums1中修改
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     * @return
     */
    public int[] sort3(int[] nums1, int m, int[] nums2, int n) {
        int k = m+n;
        for (int index = k-1,nums1Index = m-1,nums2Index = n-1; index >=0 ; index--) {
            if (nums1Index<0){//nums1已经取完,完全取nums2的值就行
                nums1[index] = nums2[nums2Index--];
            }else if (nums2Index<0){//nums1已经取完,倒叙插入结束
                break;
            }else if (nums1[nums1Index]>nums2[nums2Index]){
                //nums1的元素大于nums2,取nums1的值
                nums1[index] = nums1[nums1Index--];
            }else {
                //nums2的元素大于等于nums1,取nums2的值
                nums1[index] = nums2[nums2Index--];
            }
        }
        return nums1;
    }

}
